package 动态规划.背包问题;

import java.util.Scanner;

/**
 * 	（最朴素的方法就是在01背包的基础上加一层循环）（）
 * */
public class 完全背包问题2 {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int m=sc.nextInt();
		int n=sc.nextInt();
		int[] dp=new int[m+1];
		int[] w=new int[n+1];
		int[] c=new int[n+1];
		for(int i=1;i<=n;i++) {
			w[i]=sc.nextInt();
			c[i]=sc.nextInt();
		}
		long begin,end;
		begin=System.currentTimeMillis();
		
		for(int x=1;x<=n;x++) {
			for(int y=m;y>=1;y--)
				for(int k=0;k<=y/w[x];k++) {	//	y/w[x]表示在容量为y的情况下，最多能拿走几次当前物品
					if(y>=w[x])
						dp[y]=max(dp[y],dp[y-k*w[x]]+k*c[x]);
				}
			/*======打印dp表=======*/
			for(int i:dp)
				System.out.print(i+" ");
			System.out.println();
		}
		
		System.out.println("最多能拿"+dp[m]+"元");
		end=System.currentTimeMillis();
		System.out.println("耗时"+(end-begin));
		sc.close();
	}
	
	
	private static int max(int i, int j) {
		return i>j?i:j;
	}
}
